package _3sort.src;

public class _8RadixSort {
    public static void main(String[] args) {
        int[] nums = {5, 68, 6, 3, 8, 52, 2, 6};
        System.out.print("未排序的数组：");
        for (int num : nums) {
            System.out.print(num+" ");
        }
        System.out.println();
        radix(nums);
        System.out.print("排序后的数组：");
        for (int num : nums) {
            System.out.print(num+" ");
        }
    }

    /**
     * 获取最大值的位数
     * @param nums：传入的数组
     * @return：数组中最大值的位数
     */
    public static int maxbits(int[] nums) {
        //第一步先找出数组中的最大值
        int max = nums[0];
        for (int num : nums) {
            max = Math.max(max, num);
        }
        int count=0;//记录数字的位数
        while (max != 0) {
            count++;
            max = max / 10;
        }
        return count;
    }

    public static void radix(int[] nums) {
        if (nums == null || nums.length < 2) {
            return;
        }
        radixSort(nums, 0, nums.length - 1, maxbits(nums));
    }

    /**
     * 进行排序
     * @param nums：传入的数组
     * @param L：传入数组的第一个索引，其实就是相关于0，这里没有相关的递归
     * @param R：传入数组的长度-1，即最后一个索引
     * @param digit：获取的最大值的位数，用于进行后续循环的遍历次数
     */
    public static void radixSort(int[] nums, int L, int R, int digit) {
        final int radix=10;//表示0-9的个数创造的不变值，其实就是对应的10个桶的个数
        int i = 0, j = 0;
        int[] bucket = new int[R - L + 1];//表示要排序的数组的个数
        for (int k = 1; k <= digit; k++) {//表示进桶和出桶的次数
            int[] count = new int[radix];
            //对相应的数字位（0-9）继续判断，判断单个位数上的数字是谁后进行数字个数的增加
            for (i = L; i <= R; i++) {
                j = getDigit(nums[i], k);//获取当前的数字位
                count[j]++;
            }
            //获取数组之前位数的前缀和，从数字1的位数开始，0前面没有数字，radix的值为10
            for (i = 1; i < radix; i++) {
                count[i] += count[i - 1];
            }
            //进行相关的出桶操作
            for (i = R; i >= L; i--) {
                j = getDigit(nums[i],k);
                bucket[count[j] - 1] = nums[i];
                count[j]--;
            }
            //进行上面的操作后，就把某个位上的数字按照从小到大排列出来了
            System.arraycopy(bucket,0,nums,L,R-L+1);
           /* for (i = L, j = 0; i <= R; i++, j++) {
                nums[i] = bucket[j];
            }*/
        }
    }

    /**
     * 获取当前n位置的数字位
     * @param num：传入的数字
     * @param n：传入的位数
     * @return：特定位数的值
     */
    public static int getDigit(int num, int n) {
        /*for (int i = 0; i < n-1; i++) {
            num = num / 10;
        }
        return num % 10;*/
        //上面代码等价于
        return (num / (int)Math.pow(10, n-1)) % 10;
    }

}
